
\section{求先序排列(p1030)}

\subsection{题目描述}

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8）。

\subsection{输入格式}
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

\subsection{输出格式}
1行，表示一棵二叉树的先序。

\subsection{输入输出样例}
\textbf{输入样例}
\begin{lstlisting}
BADC
BDCA
\end{lstlisting}
\textbf{输出样例}
\begin{lstlisting}
ABCD
\end{lstlisting}

\subsection{分析}
本题的重点是重建二叉树，对二叉树来说，已知先序遍历和中序遍历可以重建，已知后序遍历和中序遍历可以重建，
但已知先序遍历和后序遍历不能重建。

对本题来说，可以通过后续遍历的最后一个字母找到树根。然后用在中序遍历中查找这个树根的字母，可以用这个字
母把树继续分为“左子树”和“右子树”。然后尝试用同样的方法去重建右子树和左子树。注意，在后续遍历字符串中去
掉最后一个字母之后，剩下的最后一个字母应该是右子树的根。

本地对于OI选手最大的难点是指针操作，OI题目中指针操作比较少。如果对指针不熟悉，在比赛的时遇到类似题目，
node数组的整数索引代替指针操作。

\subsection{代码}
\begin{lstlisting}
#include <stdio.h>

#define N 20

typedef struct node_s {
	struct node_s *left, *right; 
	char val; 
}node_t; 

char preorder[N], inorder[N], postorder[N]; 

node_t node[N]; 
int nr_node; 

node_t *alloc_node(char v)
{
	node_t *n=&node[nr_node++]; 
	n->left = NULL; 
	n->right = NULL; 
	n->val = v; 
	return n; 
}

node_t *build_tree(char **post_pp, char *in_p)
{
	char *left, *right; 
	char v = **post_pp; 
	node_t *n = alloc_node(v); 
	if (*post_pp==postorder)
		return n; 
	left=in_p; 
	for(right=in_p; *right!=v; right++); 
	*right++ = '\0'; 
	if (*right) {
		--(*post_pp); 
		n->right = build_tree(post_pp, right); 
	}
	if (*left) {
		--(*post_pp); 
		n->left = build_tree(post_pp, left); 
	}
	return n; 
}

void walk_preorder(node_t *n)
{
	printf("%c", n->val); 
	if (n->left)
		walk_preorder(n->left); 
	if (n->right)
		walk_preorder(n->right); 
}

void walk_preorder_dbg(int lvl, node_t *n)
{
	int i; 
	for(i=0; i<lvl; i++) printf(" "); 
	printf("val=%c\n", n->val); 
	if (n->left) {
		for(i=0; i<lvl; i++) printf(" "); 
		printf("left: "); 
		walk_preorder_dbg(lvl+1, n->left); 
	}
	if (n->right) {
		for(i=0; i<lvl; i++) printf(" "); 
		printf("right: "); 
		walk_preorder_dbg(lvl+1, n->right); 
	}
}

int main()
{
	node_t *n;
	char *p; 
	scanf("%s", inorder); 
	scanf("%s", postorder); 
	for(p=postorder; *p; p++); 
	p--; 
	n = build_tree(&p, inorder); 
	walk_preorder(n); 
	printf("\n"); 
	return 0; 
}
\end{lstlisting}

